class Solution
{
public:
    int threeSumClosest(vector<int>& nums, int target)
    {
        sort(nums.begin(), nums.end());
        int min_diff = INT_MAX;

        int ans, n = nums.size();
        for (int i = 0; i < n - 2; i++)
        {
            int x = nums[i];
            if (i > 0 && x == nums[i - 1]) continue;

            int t = x + nums[i + 1] + nums[i + 2];
            if (t > target)
            {
                if (t - target < min_diff)
                    ans = t;
                break;
            }

            t = x + nums[n - 2] + nums[n - 1];
            if (t < target)
            {
                if (target - t < min_diff)
                {
                    min_diff = target - t;
                    ans = t;
                }
                continue;
            }

            int j = i + 1, k = n - 1;
            while (j < k)
            {
                t = x + nums[j] + nums[k];
                if (t == target) return t;

                if (t > target)
                {
                    if (t - target < min_diff)
                    {
                        min_diff = t - target;
                        ans = t;
                    }
                    k--;
                }
                else
                {
                    if (target - t < min_diff)
                    {
                        min_diff = target - t;
                        ans = t;
                    }
                    j++;
                }
            }
        }
        return ans;
    }
};